package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.ListNode;

public class ReverseKGroup {

    /**
     * 顺序遍历，每k个翻转一次，翻转就是长度为k的单个链表翻转
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) {
            return head;
        }

        ListNode root = new ListNode(-1, head);
        reverseSubGroup(root, k);
        int index = 1;
        ListNode tail = root.next;
        while (tail != null) {
            if (index == k && tail.next != null) {
                reverseSubGroup(tail, k);
                index = 0;
            }
            tail = tail.next;
            index++;
        }
        return root.next;
    }

    public void reverseSubGroup(ListNode pNode, int k) {
        int index = 1;
        ListNode prev = pNode.next, tail = prev.next;
        while (tail != null && index < k) {
            ListNode t = tail.next;
            tail.next = pNode.next;
            pNode.next = tail;
            tail = t;
            prev.next = t;
            index++;
        }
        if (index < k){
            prev = pNode.next;
            tail = prev.next;
            while (tail != null){
                ListNode t = tail.next;
                tail.next = pNode.next;
                pNode.next = tail;
                tail = t;
                prev.next = t;
            }
        }
    }

}
